//<p>给你两个单词&nbsp;<code>word1</code> 和&nbsp;<code>word2</code>， <em>请返回将&nbsp;<code>word1</code>&nbsp;转换成&nbsp;<code>word2</code> 所使用的最少操作数</em> &nbsp;。</p>
//
//<p>你可以对一个单词进行如下三种操作：</p>
//
//<ul>
//	<li>插入一个字符</li>
//	<li>删除一个字符</li>
//	<li>替换一个字符</li>
//</ul>
//
//<p>&nbsp;</p>
//
//<p><strong>示例&nbsp;1：</strong></p>
//
//<pre>
//<strong>输入：</strong>word1 = "horse", word2 = "ros"
//<strong>输出：</strong>3
//<strong>解释：</strong>
//horse -&gt; rorse (将 'h' 替换为 'r')
//rorse -&gt; rose (删除 'r')
//rose -&gt; ros (删除 'e')
//</pre>
//
//<p><strong>示例&nbsp;2：</strong></p>
//
//<pre>
//<strong>输入：</strong>word1 = "intention", word2 = "execution"
//<strong>输出：</strong>5
//<strong>解释：</strong>
//intention -&gt; inention (删除 't')
//inention -&gt; enention (将 'i' 替换为 'e')
//enention -&gt; exention (将 'n' 替换为 'x')
//exention -&gt; exection (将 'n' 替换为 'c')
//exection -&gt; execution (插入 'u')
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>0 &lt;= word1.length, word2.length &lt;= 500</code></li>
//	<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li>
//</ul>
//<div><div>Related Topics</div><div><li>字符串</li><li>动态规划</li></div></div><br><div><li>👍 2443</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

/**
 * 编辑距离
 * @author DY Rising
 * @date 2022-06-27 20:06:41
 */
public class P72_EditDistance{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P72_EditDistance().new Solution();
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }

        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}

//leetcode submit region end(Prohibit modification and deletion)

}
